package com.sort;

import java.util.Arrays;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/25 18:29
 * @description 荷兰国旗问题
 */
public class NetherlandsFlagQuestion {

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 4, 5, 6, 7, 6, 5};
        process(arr, 5);
        System.out.println(Arrays.toString(arr));
        process2(arr,5);
        System.out.println(Arrays.toString(arr));

    }

    //给定一个数组arr 和一个数num 请吧小于等于num的数放在数组的左边
    //大于num的数放在num的右边 要求空间复杂度o1  时间复杂度0n
    /*
    思路
    定义两个指针 定义一个左边界
    遍历数组 如果arr[i] <= num 则arr[i]和左边界的后一个元素进行交换
    如果 arr[i] > num 跳过继续往前遍历
     */
    public static void process(int[] arr, int num) {
        int left = -1;
        int i = 0;
        int right = arr.length;
        while (i < right) {
            if (arr[i] <= num) {
                swap(arr, ++left, i++);
            } else i++;//继续往前走
        }
    }


    //给定一个数组arr 和一个数num
    //小于num的数放在数组的左边
    //等于num的数放中间
    //大于num的数放在num的右边 要求空间复杂度o1  时间复杂度0n
    /*
    思路: 最好自己画图理解
    定义一个左边界 再定义一个右边界
    开始遍历数组 如果arr[i] < num 交换arr[i]和左边界前一个的数据
    如果arr[i] == num 不做交换 i++
    如果arr[i] > num 交换右边界的前一个元素和arr[i] 并且i不动
     */
    public static void process2(int[] arr, int num) {
        int left = -1;
        int i = 0;
        int right = arr.length;
        while (i < right) {
            if (arr[i] < num) {
                swap(arr, ++left, i++);
            } else if (arr[i] == num) {
                i++;
            } else {
                swap(arr, --right, i);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        //因为涉及到自己和自己交换 不能用异或了
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
